package leetcode_2501_2600;

import java.util.*;

public class LeeCode_2555_failed {
    public static void main(String[] args) {
        System.out.println(maximizeWin(new int[]{1, 1, 2, 2, 3, 3, 5}, 2));
        System.out.println(maximizeWin(new int[]{1, 2, 3, 4}, 0));
    }

    private static int maximizeWin(int[] prizePositions, int k) {
        int n = prizePositions.length;
        int ans = 0, max = 0, l = 0, r = 0;
        HashMap<Integer, List<int[]>> map = new HashMap<>();
        for (int i = 0; i < prizePositions.length; i++) {
            int endI = bigger(prizePositions, prizePositions[i] + k);
            if (endI == -1) {
                if (n - i > max) {
                    max = n - i;
                    l = i;
                    r = n - 1;
                    List<int[]> list = new ArrayList<>();
                    list.add(new int[]{l, r});
                    map.put(max, list);
                }
                if (!map.containsKey(n - i)){
                    List<int[]> list = new ArrayList<>();
                    list.add(new int[]{i, n - 1});
                    map.put(n - i, list);
                }else {
                    map.get(n - i).add(new int[]{i, n - 1});
                }
                break;
            }
            if (endI - i + 1 > max) {
                max = endI - i;
                l = i;
                r = endI;
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{l, r});
                map.put(max, list);
            }
            if (!map.containsKey(endI - i + 1)){
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{i, endI});
                map.put(max, list);
            }else {
                map.get(endI - i + 1).add(new int[]{i, endI});
            }
        }
        ans += max;
        int max2 = 0;
        for (Integer key : map.keySet()) {
            List<int[]> list = map.get(key);
            for (int[] p : list) {
                max2 = Math.max(max2, getMax(prizePositions, k, n, p[0], p[1]));
            }
        }
        ans += max2;
        return ans;
    }

    private static int getMax(int[] prizePositions, int k, int n, int l, int r) {
        int max;
        max = 0;
        for (int i = 0; i < prizePositions.length; i++) {
            int endI = bigger(prizePositions, prizePositions[i] + k);
            if (endI == -1) {
                if (l >= i) {
                    max = Math.max(max, l - i);
                } else {
                    max = Math.max(max, n - i);
                }
                break;
            }
            if (l >= i && l <= endI) {
                max = Math.max(max, l - i);
            } else if (r >= i && r <= endI) {
                max = Math.max(max, endI - r);
            }
        }
        return max;
    }

    private static int bigger(int[] arr, int goal) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (arr[m] <= goal) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        if (arr[l] < goal) {
            return -1;
        }
        return l;
    }
}
